package leetcode_jz_offer.day7_bin_tree;

/**
 * 输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)
 * B是A的子结构， 即 A中有出现和B相同的结构和节点值
 **/

/**
 * 先序遍历树A中的每个节点nA 函数: isSubStructure(A, B)）
 * 判断树 AA 中 以 nA为根节点的子树 是否包含树B。（对应函数 recur(A, B)）
 */
public class Num26_B是否是A的子树 {
    private class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
  }
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if(A==null&&B==null){
            return true;
        }
        if(A==null||B==null){
            return false;
        }
        //recur：A中是否包含B
        return recur(A,B)||isSubStructure(A.left,B)||isSubStructure(A.right,B);
    }
    //方法1（更优）
//    //判断A中是否包含B
//    private boolean recur(TreeNode A, TreeNode B) {
//        if(B==null){
//            //B走到null,B遍历完毕了，说明B一定在A中包含。不包含的话中间值不等时就会直接退出
//            return true;
//        }
//        if(A==null){
//            //走到最后了A还在遍历，说明没有值匹配
//            return false;
//        }
//        if(A.val!=B.val){
//            return false;
//        }
//        //值相等，继续遍历下一个左右子树对应结点
//        return recur(A.left,B.left)&&recur(A.right,B.right);
//    }
    //方法2：判断A和BA.left和B或A.right和B是否相等【判断pq是否相等，相等则true，包含关系】
    public boolean recur(TreeNode p, TreeNode q) {
        if(p==null&&q==null){
            return true;
        }
        if(p!=null&&q==null){//注意这一步，当A没有遍历完但B走到了最后，说明B的值在A中已经连续找到完了，也是包含关系。如[10 12 6 8 3 11][10 12 6 8]
            return true;
        }
        if(p==null){//A走到最后还没有值
            return false;
        }
        if(p.val!=q.val){//两棵树根节点的值不相等
            return false;
        }
        //此时两个根节点值相等，再判断子树是否值相等
        return recur(p.left, q.left) && recur(p.right, q.right);
//        return p.val==q.val&& isSameTree(p.left, q.left) && isSameTree(p.right, q.right);//上面几行的简写

    }
}
/**
 * recur(A, B) 函数：
 *
 * 终止条件：
 * 当节点 BB 为空：说明树 BB 已匹配完成（越过叶子节点），因此返回 truetrue ；
 * 当节点 AA 为空：说明已经越过树 AA 叶子节点，即匹配失败，返回 falsefalse ；
 * 当节点 AA 和 BB 的值不同：说明匹配失败，返回 falsefalse ；
 * 返回值：
 * 判断 AA 和 BB 的左子节点是否相等，即 recur(A.left, B.left) ；
 * 判断 AA 和 BB 的右子节点是否相等，即 recur(A.right, B.right) ；
 * isSubStructure(A, B) 函数：
 *
 * 特例处理： 当 树 AA 为空 或 树 BB 为空 时，直接返回 falsefalse ；
 * 返回值： 若树 BB 是树 AA 的子结构，则必满足以下三种情况之一，因此用或 || 连接；
 * 以 节点 AA 为根节点的子树 包含树 BB ，对应 recur(A, B)；
 * 树 BB 是 树 AA 左子树 的子结构，对应 isSubStructure(A.left, B)；
 * 树 BB 是 树 AA 右子树 的子结构，对应 isSubStructure(A.right, B)；
 * 链接：https://leetcode.cn/problems/shu-de-zi-jie-gou-lcof/solution/mian-shi-ti-26-shu-de-zi-jie-gou-xian-xu-bian-li-p/
 */